
def insertion_sort(array):
    for index in range(1, len(array)):
        current = index
        while array[current] < array[current - 1] and current > 0:
            array[current], array[current - 1] = array[current - 1], array[current]
            current -= 1


def test_insertion_sort():
    array = [1, 2, 3, 4, 5, 6]
    insertion_sort(array)
    assert 1 == array[0]
    assert 6 == array[5]
    assert 3 == array[2]

    array = [6, 5, 4, 3, 2, 1]
    insertion_sort(array)
    assert 1 == array[0]
    assert 6 == array[5]
    assert 3 == array[2]

    array = [2, 3, 1, 4, 6, 5]
    insertion_sort(array)
    assert 1 == array[0]
    assert 6 == array[5]
    assert 3 == array[2]
